<!DOCTYPE html>
<html>
<head>
<title>寻找最接近的回文数</title>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<style type="text/css">
/* GitHub stylesheet for MarkdownPad (http://markdownpad.com) */
/* Author: Nicolas Hery - http://nicolashery.com */
/* Version: b13fe65ca28d2e568c6ed5d7f06581183df8f2ff */
/* Source: https://github.com/nicolahery/markdownpad-github */

/* RESET
=============================================================================*/

html, body, div, span, applet, object, iframe, h1, h2, h3, h4, h5, h6, p, blockquote, pre, a, abbr, acronym, address, big, cite, code, del, dfn, em, img, ins, kbd, q, s, samp, small, strike, strong, sub, sup, tt, var, b, u, i, center, dl, dt, dd, ol, ul, li, fieldset, form, label, legend, table, caption, tbody, tfoot, thead, tr, th, td, article, aside, canvas, details, embed, figure, figcaption, footer, header, hgroup, menu, nav, output, ruby, section, summary, time, mark, audio, video {
  margin: 0;
  padding: 0;
  border: 0;
}

/* BODY
=============================================================================*/

body {
  font-family: Helvetica, arial, freesans, clean, sans-serif;
  font-size: 14px;
  line-height: 1.6;
  color: #333;
  background-color: #fff;
  padding: 20px;
  max-width: 960px;
  margin: 0 auto;
}

body>*:first-child {
  margin-top: 0 !important;
}

body>*:last-child {
  margin-bottom: 0 !important;
}

/* BLOCKS
=============================================================================*/

p, blockquote, ul, ol, dl, table, pre {
  margin: 15px 0;
}

/* HEADERS
=============================================================================*/

h1, h2, h3, h4, h5, h6 {
  margin: 20px 0 10px;
  padding: 0;
  font-weight: bold;
  -webkit-font-smoothing: antialiased;
}

h1 tt, h1 code, h2 tt, h2 code, h3 tt, h3 code, h4 tt, h4 code, h5 tt, h5 code, h6 tt, h6 code {
  font-size: inherit;
}

h1 {
  font-size: 28px;
  color: #000;
}

h2 {
  font-size: 24px;
  border-bottom: 1px solid #ccc;
  color: #000;
}

h3 {
  font-size: 18px;
}

h4 {
  font-size: 16px;
}

h5 {
  font-size: 14px;
}

h6 {
  color: #777;
  font-size: 14px;
}

body>h2:first-child, body>h1:first-child, body>h1:first-child+h2, body>h3:first-child, body>h4:first-child, body>h5:first-child, body>h6:first-child {
  margin-top: 0;
  padding-top: 0;
}

a:first-child h1, a:first-child h2, a:first-child h3, a:first-child h4, a:first-child h5, a:first-child h6 {
  margin-top: 0;
  padding-top: 0;
}

h1+p, h2+p, h3+p, h4+p, h5+p, h6+p {
  margin-top: 10px;
}

/* LINKS
=============================================================================*/

a {
  color: #4183C4;
  text-decoration: none;
}

a:hover {
  text-decoration: underline;
}

/* LISTS
=============================================================================*/

ul, ol {
  padding-left: 30px;
}

ul li > :first-child, 
ol li > :first-child, 
ul li ul:first-of-type, 
ol li ol:first-of-type, 
ul li ol:first-of-type, 
ol li ul:first-of-type {
  margin-top: 0px;
}

ul ul, ul ol, ol ol, ol ul {
  margin-bottom: 0;
}

dl {
  padding: 0;
}

dl dt {
  font-size: 14px;
  font-weight: bold;
  font-style: italic;
  padding: 0;
  margin: 15px 0 5px;
}

dl dt:first-child {
  padding: 0;
}

dl dt>:first-child {
  margin-top: 0px;
}

dl dt>:last-child {
  margin-bottom: 0px;
}

dl dd {
  margin: 0 0 15px;
  padding: 0 15px;
}

dl dd>:first-child {
  margin-top: 0px;
}

dl dd>:last-child {
  margin-bottom: 0px;
}

/* CODE
=============================================================================*/

pre, code, tt {
  font-size: 12px;
  font-family: Consolas, "Liberation Mono", Courier, monospace;
}

code, tt {
  margin: 0 0px;
  padding: 0px 0px;
  white-space: nowrap;
  border: 1px solid #eaeaea;
  background-color: #f8f8f8;
  border-radius: 3px;
}

pre>code {
  margin: 0;
  padding: 0;
  white-space: pre;
  border: none;
  background: transparent;
}

pre {
  background-color: #f8f8f8;
  border: 1px solid #ccc;
  font-size: 13px;
  line-height: 19px;
  overflow: auto;
  padding: 6px 10px;
  border-radius: 3px;
}

pre code, pre tt {
  background-color: transparent;
  border: none;
}

kbd {
    -moz-border-bottom-colors: none;
    -moz-border-left-colors: none;
    -moz-border-right-colors: none;
    -moz-border-top-colors: none;
    background-color: #DDDDDD;
    background-image: linear-gradient(#F1F1F1, #DDDDDD);
    background-repeat: repeat-x;
    border-color: #DDDDDD #CCCCCC #CCCCCC #DDDDDD;
    border-image: none;
    border-radius: 2px 2px 2px 2px;
    border-style: solid;
    border-width: 1px;
    font-family: "Helvetica Neue",Helvetica,Arial,sans-serif;
    line-height: 10px;
    padding: 1px 4px;
}

/* QUOTES
=============================================================================*/

blockquote {
  border-left: 4px solid #DDD;
  padding: 0 15px;
  color: #777;
}

blockquote>:first-child {
  margin-top: 0px;
}

blockquote>:last-child {
  margin-bottom: 0px;
}

/* HORIZONTAL RULES
=============================================================================*/

hr {
  clear: both;
  margin: 15px 0;
  height: 0px;
  overflow: hidden;
  border: none;
  background: transparent;
  border-bottom: 4px solid #ddd;
  padding: 0;
}

/* TABLES
=============================================================================*/

table th {
  font-weight: bold;
}

table th, table td {
  border: 1px solid #ccc;
  padding: 6px 13px;
}

table tr {
  border-top: 1px solid #ccc;
  background-color: #fff;
}

table tr:nth-child(2n) {
  background-color: #f8f8f8;
}

/* IMAGES
=============================================================================*/

img {
  max-width: 100%
}
</style>
</head>
<body>
<h1>寻找最接近的回文数</h1>
<hr />
<h2>1. 题目</h2>
<p>题目来自LeetCode:
    <a href="https://leetcode-cn.com/problems/find-the-closest-palindrome/">https://leetcode-cn.com/problems/find-the-closest-palindrome/</a></p>
<p>题目：</p>
<pre><code>给定一个整数n，找到与它最近的回文数（不包括自身）。
“最近的”定义为两个整数差的绝对值最小。
eg.
    输入: &quot;123&quot;
    输出: &quot;121&quot;

注意:
    n是由字符串表示的正整数。
    如果有多个结果，返回最小的那个。
</code></pre>

<h2>2. 思路：</h2>
<pre><code>保留高位数字，改变低位数字，利用前半部分n_left（高位数）做镜像生成回文数
值最接近的回文数可能为n_left、n_left+1或n_left-1产生的回文数，三者比较即可
特殊情况单独处理
截取n_left时分n的长度为奇数和偶数两种情况
参考：
    https://leetcode-cn.com/problems/find-the-closest-palindrome/solution/zhao-gui-lu-by-heng-29/
    https://leetcode-cn.com/problems/find-the-closest-palindrome/solution/jing-xiang-dui-bi-by-dui-fang-xian-ru-chen-si/
</code></pre>

<h2>3. Python代码：</h2>
<pre><code>def NearestPalindromic(n):

    try:
        n_int = int(n)
        if n_int &lt; 0:
            print('n小于0！')
            return None
    except:
        print('输入n应为字符串表示的正整数！')
        return None

    lenn = len(n)
    lenn_half = lenn // 2

    # 特殊情况：只有一位数
    if lenn_half == 0:
        return '1' if n == '0' else str(n_int-1)

    # 特殊情况：开头1，中间若干个0，末尾一个数字
    if n[0] == '1' and not any([int(x) for x in n[1:-1]]):
        # 若最后一位为0或1，结果应全由9构成；若最后一位为其他，则将最后一位改为1即可
        if n[-1] in ['0', '1']:
            return '9' * (lenn-1)
        else:
            return n[:-1] + '1'

    # 特殊情况：全是9
    if not any([int(x)-9 for x in n]):
        return str(n_int+2)

    # n为偶数位
    if lenn % 2 == 0:
        n_left = n[:lenn_half]
        tgt_n = n_left + n_left[::-1] # 原数反转
        tmp = str(int(n_left)-1)
        tgt_sml = tmp + tmp[::-1] # 小的目标值
        tmp = str(int(n_left)+1)
        tgt_big = tmp + tmp[::-1] # 大的目标值
    else:
        n_left = n[:lenn_half]
        tgt_n = n_left + n[lenn_half] + n_left[::-1]
        tmp = str(int(n[:lenn_half+1])-1)
        tgt_sml = tmp + tmp[:-1][::-1]
        tmp = str(int(n[:lenn_half+1])+1)
        tgt_big = tmp + tmp[:-1][::-1]

    # 从大到小排除其他两个结果
    ans = tgt_big
    for t in [tgt_n, tgt_sml]:
        dif = abs(int(t)-n_int)
        if dif &gt; 0 and dif &lt;= abs(int(ans)-n_int):
            ans = t

    return ans


if __name__ == '__main__':
    n = '123'
    print(n+': ——&gt;', NearestPalindromic(n))

    n = '1234'
    print(n+': ——&gt;', NearestPalindromic(n))

    n = '1'
    print(n+': ——&gt;', NearestPalindromic(n))

    n = '10'
    print(n+': ——&gt;', NearestPalindromic(n))

    n = '102'
    print(n+': ——&gt;', NearestPalindromic(n))

    n = '100'
    print(n+': ——&gt;', NearestPalindromic(n))

    n = '600'
    print(n+': ——&gt;', NearestPalindromic(n))

    n = '198'
    print(n+': ——&gt;', NearestPalindromic(n))

    n = '598'
    print(n+': ——&gt;', NearestPalindromic(n))

    n = '101'
    print(n+': ——&gt;', NearestPalindromic(n))

    n = 'abc'
    print(n+': ——&gt;', NearestPalindromic(n))

    n = '-102'
    print(n+': ——&gt;', NearestPalindromic(n))

    n = '22'
    print(n+': ——&gt;', NearestPalindromic(n))

    n = '11'
    print(n+': ——&gt;', NearestPalindromic(n))

    n = '1002'
    print(n+': ——&gt;', NearestPalindromic(n))

    n = '1000'
    print(n+': ——&gt;', NearestPalindromic(n))

    n = '88'
    print(n+': ——&gt;', NearestPalindromic(n))

    n = '11911'
    print(n+': ——&gt;', NearestPalindromic(n))

    n = '1283'
    print(n+': ——&gt;', NearestPalindromic(n))
</code></pre>


</body>
</html>
<!-- This document was created with MarkdownPad, the Markdown editor for Windows (http://markdownpad.com) -->
